public class code3 {
    public boolean wordBreak(String s, List<String> wordDict) {
        //优化1：将字典里面的单词存到哈希表中，在哈希表中找子串是否存在
        Set<String> hash = new HashSet<>(wordDict);

        int n = s.length();

        boolean[] dp = new boolean[n+1];//dp[i]：0-i区间内的字符串能否被拼接成功

        //初始化
        dp[0] = true;

        s = " " + s;//处理下标的映射关系(s的起始位置是从1开始的)

        for(int i=1;i<=n;i++) {
            for(int j=i;j>=1;j--) {
                if(dp[j-1]==true && hash.contains(s.substring(j,i+1))) {//左闭右开
                    dp[i] = true;
                    break;//优化2：只要在哈希表中找到一个单词即可，找到了就不用继续找下一个了
                }
            }
        }
        return dp[n];
    }
}
